|
In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. We say ''an'' apex, not ''the'' apex because an apex graph may have more than one apex (for example, in the minimal nonplanar graphs ''K''5 or ''K''3,3, every vertex is an apex). The apex graphs include graphs that are themselves planar, in which case again every vertex is an apex. The null graph is also counted as an apex graph even though it has no vertex to remove. Apex graphs are closed under the operation of taking minors and play a role in several other aspects of graph minor theory: linkless embedding,〔 Hadwiger's conjecture,〔.〕 YΔY-reducible graphs,〔 and relations between treewidth and graph diameter.〔 ==Characterization and recognition== Apex graphs are closed under the operation of taking minors: contracting any edge, or removing any edge or vertex, leads to another apex graph. For, if ''G'' is an apex graph with apex ''v'', then any contraction or removal that does not involve ''v'' preserves the planarity of the remaining graph, as does any edge removal of an edge incident to ''v''. If an edge incident to ''v'' is contracted, the effect on the remaining graph is equivalent to the removal of the other endpoint of the edge. And if ''v'' itself is removed, any other vertex may be chosen as the apex.〔 Because they form a minor-closed family of graphs, the apex graphs have a forbidden graph characterization: there exists a finite set ''A'' of minor-minimal non-apex graphs such that a graph is an apex graph if and only if it does not contain as a minor any graph in ''A''. The forbidden minors for the apex graphs include the seven graphs of the Petersen family, three disconnected graphs formed from the disjoint unions of two of ''K''5 and ''K''3,3, and many other graphs. However, a complete description of the graphs in ''A'' remains unknown.〔.〕 Despite the unknown set of forbidden minors, it is possible to test whether a given graph is an apex graph, and if so, to find an apex for the graph, in linear time. More generally, for any fixed constant ''k'', it is possible to recognize in linear time the ''k''-apex graphs, the graphs in which the removal of some carefully chosen set of at most ''k'' vertices leads to a planar graph.〔.〕 If ''k'' is variable, however, the problem is NP-complete.〔.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Apex graph」の詳細全文を読む スポンサード リンク
|